package com.datastructures2.graph.最短路径;

import com.datastructures2.graph.有向图.TopologicalSort;

import java.util.Stack;

/**
 * 加权有向无环图的最长路径
 * @author MaoLin Wang
 * @date 2020/2/2416:38
 */
public class AcyclicLP {
    private double[] distTo;
    private DirectedEdge[] edgeTo;

    public AcyclicLP(EdgeWeightedDigraph digraph,int s) {
        distTo=new double[digraph.V()];
        edgeTo=new DirectedEdge[digraph.V()];

        for (int i = 0; i < digraph.V(); i++) {
            distTo[i]=Double.NEGATIVE_INFINITY;
        }
        distTo[s]=0.0;
        TopologicalSort sort=new TopologicalSort(digraph);
        if (sort.order()==null){
            throw new IllegalArgumentException("参数错误");
        }
        for (int w:sort.order()){
            relax(digraph,w);
        }
    }

    private void relax(EdgeWeightedDigraph digraph, int v) {
        for (DirectedEdge edge:digraph.adj(v)){
            int to=edge.to(),from = edge.from();
            if (distTo[to]<distTo[from]+edge.weight()){
                distTo[to]=distTo[from]+edge.weight();
                edgeTo[to]=edge;
            }
        }
    }
    public double distTo(int v) {
        return distTo[v];
    }


    public boolean hasPathTo(int v) {
        return distTo[v] > Double.NEGATIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Stack<DirectedEdge> path=new Stack<>();
        for (DirectedEdge edge=edgeTo[v];edge!=null;edge=edgeTo[edge.from()]){
            path.push(edge);
        }
        return path;
    }
}
